We give a novel application of algebraic logic to first order logic. A new, flexible construction is presented for representable but not completely representable atomic relation and cylindric algebras of dimension n (for finite n > 2) with the additional property that they are one-generated and the set of all n by n atomic matrices forms a cylindric basis. We use this construction to show that the classical Henkin-Orey omitting types theorem fails for the finite variable fragments of first order (...) logic as long as the number of variables available is > 2 and we have a binary relation symbol in our language. We also prove a stronger result to the effect that there is no finite upper bound for the extra variables needed in the witness formulas. This result further emphasizes the ongoing interplay between algebraic logic and first order logic. (shrink)

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n ≤ w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin's axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey's omitting types theorem fails for Ln, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. Ln has been recently (and quite extensively) studied as a many-dimensional (...) modal logic. (shrink)

SC , CA , QA and QEA stand for the classes of Pinter's substitution algebras, Tarski's cylindric algebras, Halmos' quasipolyadic algebras, and quasipolyadic equality algebras of dimension , respectively. Generalizing a result of Németi on cylindric algebras, we show that for K {SC, CA, QA, QEA} and ordinals , the class Nr K of -dimensional neat reducts of -dimensional K algebras, though closed under taking homomorphic images and products, is not closed under forming subalgebras (i.e. is not a variety) if (...) and only if > 1.From this it easily follows that for 1 , the operation of forming -neat reducts of algebras in K does not commute with forming subalgebras, a notion to be made precise. (shrink)

We give a new characterization of the class of completely representable cylindric algebras of dimension 2 #lt; n w via special neat embeddings. We prove an independence result connecting cylindric algebra to Martin''s axiom. Finally we apply our results to finite-variable first order logic showing that Henkin and Orey''s omitting types theorem fails for L n, the first order logic restricted to the first n variables when 2 #lt; n#lt;w. L n has been recently (and quite extensively) studied as a (...) many-dimensional modal logic. (shrink)

Let 1 n. We show that the class NrnCAβ of n-dimensional neat reducts of β-dimensional cylindric algebras is not closed under forming elementary subalgebras. This solves a long-standing open problem of Tarski and his co-authors Andréka, Henkin, Monk and Németi. The proof uses genuine model-theoretic arguments.

We show that not all epimorphisms are surjective in certain classes of infinite dimensional cylindric algebras, Pinter's substitution algebras and Halmos' quasipolyadic algebras with and without equality. It follows that these classes fail to have the strong amalgamation property. This answers a question in [3] and a question of Pigozzi in his landmark paper on amalgamation [9]. The cylindric case was first proved by Judit Madarasz [7]. The proof presented herein is substantially different. By a result of Németi, our result (...) implies that the Beth-definability Theorem fails for certain expansions of first order logic. (shrink)

In this paper, an extension of first order logic is introduced. In such logics atomic formulas may have infinite lengths. An Omitting Types Theorem is proved.

We show that it is impossible to define a substitution operator for arbitrary representable cylindric algebras that agrees in its basic properties with the notion of substitutions introduced for dimension complemented algebras.

SC, CA, QA and QEA denote the class of Pinter’s substitution algebras, Tarski’s cylindric algebras, Halmos’ quasi-polyadic and quasi-polyadic equality algebras, respectively. Let . and . We show that the class of n dimensional neat reducts of algebras in K m is not elementary. This solves a problem in [2]. Also our result generalizes results proved in [1] and [2].

We prove several interpolation theorems for many-valued infinitary logic with quantifiers by studying expansions of MV-algebras in the spirit of polyadic and cylindric algebras. We prove for various reducts of polyadic MV-algebras of infinite dimensions that if is the free algebra in the given signature,, is in the subalgebra of generated by, is in the subalgebra of generated by and, then there exists an interpolant in the subalgebra generated by and such that. We call this a varying interpolation property because (...) the integer depends on the inequality. We also address cases where this interpolation property fails, but other weaker ones hold. One such interpolation theorem says that though an interpolant may not be found as above, an interpolant can always be found if finitely many universal quantifiers are applied to making it smaller and the same number of existential quantifiers are applied to making it bigger. This number of quantifiers also varies; it depends on the inequality. Se.. (shrink)

We redefine a system of varieties definable by a schema of equations to include finite dimensions. Then we present a technique using ultraproducts enabling one to lift results proved for every finite dimension to the transfinite. Let \(\bf Ord\) denote the class of all ordinals. Let \(\langle \mathbf{K}_{\alpha}: \alpha\in \bf Ord\rangle\) be a system of varieties definable by a schema. Given any ordinal \(\alpha\), we define an operator \(\mathsf{Nr}_{\alpha}\) that acts on \(\mathbf{K}_{\beta}\) for any \(\beta>\alpha\) giving an algebra in \(\mathbf{K}_{\alpha}\), (...) as an abstaction of taking \(\alpha\)-neat reducts for cylindric algebras. We show that for any positive \(k\), and any infinite ordinal \(\alpha\) that \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k+1}\) cannot be axiomatized by a finite schema over \(\mathbf{S}\mathsf{Nr}_{\alpha}\mathbf{K}_{\alpha+k}\) given that the result is valid for all finite dimensions greater than some fixed finite ordinal. We apply our results to cylindric algebras and Halmos quasipolyadic algebras with equality. As an application to our algebraic result we obtain a strong incompleteness theorem (in the sense that validitities are not captured by finitary Hilbert style axiomatizations) for an algebraizable extension of \(L_{\omega,\omega}\). (shrink)

Let α be an arbitrary infinite ordinal, and. In [26] we studied—using algebraic logic—interpolation and amalgamation for an extension of first order logic, call it, with α many variables, using a modal operator of a unimodal logic that contributes to the semantics. Our algebraic apparatus was the class of modal cylindric algebras. Modal cylindric algebras, briefly, are cylindric algebras of dimension α, expanded with unary modalities inheriting their semantics from a unimodal logic such as, or. When modal cylindric algebras based (...) on are just cylindric algebras, that is to say,. This paper is a sequel to [26], where we study algebraically other properties of. We study completeness and omitting types (s) for s by proving several representability results for so‐called dimension complemented and locally finite. Furthermore, we study the notion of atom‐canonicity for, the variety of n‐dimensional modal cylindric algebras. Atom canonicity, a well known persistence property in modal logic, is studied in connection to for, which is restricted to the first n variables. We further continue our study of interpolation in [26] for algebraizable extensions of by studying using both algebraic logic and category theory. Our main results on are Theorems 3.7, 4.4 & 4.6, while our main results on amalgamation are Theorems 5.7, 5.10, 5.13 & 5.16. (shrink)

Fix 2 < n < ω and let C A n denote the class of cylindric algebras of dimension n. Roughly, C A n is the algebraic counterpart of the proof theory of first-order logic restricted to the first n var...

We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable.

We give a simple new construction of representable relation algebras with non-representable completions. Using variations on our construction, we show that the elementary closure of the class of completely representable relation algebras is not finitely axiomatizable.

We prove that the existence of atomic models for countable atomic theories does not hold for Ln the first order logic restricted to n variables for finite n > 2. Our proof is algebraic, via polyadic algebras. We note that Lnhas been studied in recent times as a multi-modal logic with applications in computer science. 2000 MATHEMATICS SUBJECT CLASSIFICATION. 03C07, 03G15.